/*
 * @Author: liusheng
 * @Date: 2022-05-17 21:03:12
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-19 17:33:32
 * @Description: 剑指 Offer II 064. 神奇的字典
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 064. 神奇的字典
设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
 

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False
 

提示：

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] 仅由小写英文字母组成
dictionary 中的所有字符串 互不相同
1 <= searchWord.length <= 100
searchWord 仅由小写英文字母组成
buildDict 仅在 search 之前调用一次
最多调用 100 次 search
 

注意：本题与主站 676 题相同： https://leetcode-cn.com/problems/implement-magic-dictionary/

通过次数7,230  提交次数11,812
 */

#include "header.h"

/*
wrong solution:if both contain a word and it's off by one brother,this will return false
it should be return true
*/
class MagicDictionary {
    class Trie
    {
    public:
        Trie():children({nullptr}),isWord(false)
        {
        }

        void insert(const string & word)
        {
            Trie * node = this;
            for (char ch : word)
            {
                char chIndex = ch - 'a';
                if (!node->children[chIndex])
                {
                    node->children[chIndex] = new Trie();
                }
                node = node->children[chIndex];
            }
            node->isWord = true;
        }

        bool contains(const string & word)
        {
            Trie * node = this;
            for (char ch : word)
            {
                char chIndex = ch - 'a';
                if (!node->children[chIndex])
                {
                    return false;
                }
                node = node->children[chIndex];
            }
            return node->isWord;
        }

        bool containMismatchByOne(const string & word)
        {
            Trie * node = this;
            for (int i = 0; i < word.size(); ++i)
            {
                char ch = word[i];
                char chIndex = ch - 'a';
                if (!node->children[chIndex])
                {                   
                    for (char j = 0; j < 26; ++j)
                    {
                        if (node->children[j] != nullptr)
                        {
                            string misOneWord = word;
                            misOneWord[i] = j + 'a';
                            if (contains(misOneWord))
                            {
                                return true;
                            }
                        }
                    }
                    return false;
                }
                node = node->children[chIndex];
            }

            return false;
        }
    private:
        array<Trie *,26> children;
        bool isWord;
    };
public:
    /** Initialize your data structure here. */
    MagicDictionary() {
        root = new Trie();
    }
    
    void buildDict(vector<string> dictionary) {
        for (auto word : dictionary)
        {
            root->insert(word);
        }
    }
    
    bool search(string searchWord) {
        return root->containMismatchByOne(searchWord);
    }
private:
    Trie * root;
};

/*
Trie with recursive similarSearch
*/
class MagicDictionary {
    class Trie
    {
    public:
        Trie():children({nullptr}),isWord(false)
        {
        }

        void insert(const string & word)
        {
            Trie * node = this;
            for (char ch : word)
            {
                char chIndex = ch - 'a';
                if (!node->children[chIndex])
                {
                    node->children[chIndex] = new Trie();
                }
                node = node->children[chIndex];
            }
            node->isWord = true;
        }

        //orgCh is used by similar search when index pos char is .
        bool searchSimilar(Trie * node,const string & word,char orgCh,int pos)
        {
           if (pos == word.size())
           {
               return node->isWord;
           }

           char ch = word[pos];

           if (ch == '.')
           {
               for (char i = 0; i < 26; ++i)
               {
                   //search any character in this level
                   char tmpCh = i + 'a';
                   if (tmpCh != orgCh && node->children[i])
                   {
                       if (searchSimilar(node->children[i],word,orgCh,pos + 1))
                       {
                           return true;
                       }
                   }
               }
               return false;
           }

           if (!node->children[ch - 'a'])
           {
               return false;
           }

           return searchSimilar(node->children[ch - 'a'],word,orgCh,pos + 1);
        }
    private:
        array<Trie *,26> children;
        bool isWord;
    };
public:
    /** Initialize your data structure here. */
    MagicDictionary() {
        root = new Trie();
    }
    
    void buildDict(vector<string> dictionary) {
        for (auto word : dictionary)
        {
            root->insert(word);
        }
    }
    
    bool search(string searchWord) {
        int n = searchWord.size();
        for (int i = 0; i < n; ++i)
        {
            char tmpCh = searchWord[i];
            searchWord[i] = '.';
            if (root->searchSimilar(root,searchWord,tmpCh,0))
            {
                return true;
            }
            searchWord[i] = tmpCh;
        }

        return false;
    }
private:
    Trie * root;
};

/**
 * @brief hashMap solution
 * 
 */
class MagicDictionary {
    //collect string by length
    unordered_map<int,vector<string>> strLenMap;
public:
    /** Initialize your data structure here. */
    MagicDictionary() {

    }
    
    void buildDict(vector<string> dictionary) {
        for (auto str: dictionary)
        {
            int n = str.size();
            if (strLenMap.count(n))
            {
                strLenMap[n].push_back(str);
            }
            else
            {
                strLenMap[n] = {str};
            }
        }
    }
    
    bool search(string searchWord) {
        int n = searchWord.size();
        if (!strLenMap.count(n))
        {
            return false;
        }

        for (auto strs : strLenMap[n])
        {
            int diffCharNum = 0;
            for (int i = 0; i < n; ++i)
            {
                if (strs[i] != searchWord[i])
                {
                    ++diffCharNum;
                }
            }
            if (diffCharNum == 1)
            {
                return true;
            }
        }

        return false;
    }
};
